1. Technical Field of the Invention
The present invention generally relates to datagram routing. More particularly, the present invention relates to a method and system for efficiently routing Internet Protocol (“IP”) fragments at layer 3 through layer 7 of the Open System Interconnection (i.e., “OSI”) hierarchical model without reassembling the fragments.
2. Description of the Prior Art
Computers and communication networks, such as the Internet, provide important advantages to enterprises and individuals in today's society. Moreover, with the advent and ensuing popularity of the World Wide Web (“Web”), there has resulted a tremendous increase in volume and usage of networked computer systems. Networked computer systems, i.e., computer systems connected via communication networks including the Internet, communicate by using protocols, such as for example, TCP/IP (“Transfer Control Protocol/Internet Protocol”), which comprises a collection of protocols used in large-scale mixed-platform packet-switched networks (i.e., Internet). As will be described hereinafter with reference to FIGS. 1 through 3, this collection of protocols transfers and verifies receipt of datagrams (i.e., packets), which include header information for routing the datagrams between a source and a destination, in addition to including a payload, i.e., data, to be transmitted to the destination.
As will be appreciated in one skilled in the art, new network applications, such as server load-balancing applications, fire walls and more generally any content-based or class-of-service based routing applications typically execute datagram routing services according to a layered networking framework known as the OSI and more particularly perform routing from layer 3 (i.e., network layer 106) through layer 7 (i.e., application layer 114) of the OSI model, as particularly depicted in FIG. 1. The higher the layer in the OSI model at which content-based routing is performed, the more difficult it is to perform routing because the content-based routing information is located deeper in the datagram (i.e., deep-packet processing).
FIG. 1 is a prior art depiction of the Open System Interconnection (i.e., “OSI”) model 100 that defines a networking framework for implementing protocols in a seven-layer architecture. Each of the seven layers represents a function that is to be performed to effect communications between different computers systems over the communication network, such as the Internet. Furthermore, each layer performs services at the request of the adjacent higher layer and, in turn, requests more basic services from the adjacent lower layer. It should however be noted that most of the functionality in the OSI model exists in all communication systems, although two or three of the OSI layers may be incorporated into one layer depending upon implementation of the communication systems.
Now particularly referring to FIG. 1, the lowest of the seven hierarchical layers in the OSI model is the physical layer 102 (i.e., layer 1). The physical layer 102 performs services requested by a data link layer 104 (i.e., layer 2), the next layer on the hierarchical OSI model. The major functions and services performed by the physical layer 102 are: 1) establishment and termination of a connection to a communication medium (e.g., Internet); participation in effectively sharing communication resources among multiple users (e.g., contention resolution and flow control); and 3) conversion between representation of data in user equipment and corresponding data transmitted over communications media. The most notable physical layer interfaces include EIA RS-232 and RS-449. The data link layer 104 (i.e., layer 2) responds to service requests from the network layer 106 (i.e., layer 3) and issues service requests to the physical layer 102. Furthermore, the data link layer 104 provides functional and procedural mechanisms for transferring data between network entities and for detecting and possibly correcting errors that may occur in the physical layer 102. The most notable examples of data link protocols are: high-level data link control (“HDLC”) and advanced data communications control procedure (“ADCCP”) for point-to-point or packet-switched networks and logical link control (“LLC”) for local area networks.
Further with reference to FIG. 1, the next layer of the hierarchical OSI model is the network layer 106, (i.e., layer 3). The network layer 106 responds to service requests from the transport layer 108 and issues service requests to the data link layer 104. Furthermore, the network layer 106 provides functional and procedural mechanisms for transferring data from a source to a destination via one or more networks while maintaining the quality of service (“QoS”) requested by the transport layer 108. Additionally, the network layer 106 performs network routing, flow control, segmentation and de-segmentation, and error control functions. The next layer of the OSI model is the transport layer 108 (i.e., layer 4). The transport layer 108 responds to service requests from the session layer 110 and issues service requests to the network layer 106. The transport layer 108 provides transparent transfer of the data between the source and the destination (i.e., end-user computer systems), thereby relieving upper layers of the OSI model from any concern regarding reliable and cost-effective data transfer. The transport layer 108 functions include monitoring of data flow for ensuring proper delivery of data between the source and the destination. Furthermore the transport layer 108 provides for data correction, data fragmentation and reassembly. The most notable protocol of the transport layer is TCP, which is a main protocol in TCP/IP networks. Whereas the IP protocol deals only with packets, TCP enables two hosts to establish a connection and to exchange streams of data. TCP guarantees delivery of data and also guarantees that packets will be delivered in the same order in which they were sent.
Still further with reference to FIG. 1, the next layer of the hierarchical OSI model is the session layer 110, (i.e., layer 5). The session layer 110 responds to service requests from the presentation layer 112 (i.e., layer 6) and issues service requests to the transport layer 108. The session layer 110 provides a mechanism for managing the dialogue between end-user application processes. It provides for either duplex or half-duplex operation and establishes check-pointing, adjournment, termination, and restart procedures. The next layer of the OSI model is the presentation layer 112, which responds to service requests from the application layer 114 and issues service requests to the session layer 110. The presentation layer 112 relieves the application layer of concern regarding syntactical differences in data representation or display within the end-user systems. The most notable example of a presentation layer service would be the conversion of an EBCDIC-coded text file to an ASCII-coded file. The topmost layer of the OSI model is the application layer 114 (i.e., layer 7), which interfaces directly to and performs common application services for the end-user application processes. Furthermore, the application layer 114 issues requests to the presentation layer 112. The common application services provide semantic conversion between associated application processes. The most notable examples of common application services include: virtual file, virtual terminal, and job transfer and manipulation protocols.
FIG. 2 is a prior art depiction of an Internet protocol (“IP”) datagram 200 that illustrates an IP header 201 and a TCP header 203. IP utilizes datagrams (i.e., packets) to communicate over packet-switched networks (e.g., the Internet). The datagram 200 represents a piece of a message transmitted over the packet-switched networks. The datagram 200 comprises an IP header 201, which includes fields 202 . . . 224 and data 207. Data 207 comprises a TCP header 203, which includes fields 226–248, as well data 205. Among other things, the IP header 201 includes a source address 222 and destination address 224 for routing the datagram. Packet switching refers to the foregoing protocols that, among other things, divide a message to be sent into packets for transmission. Each packet is individually transmitted and may follow different routes to the destination address. Once all the packets forming the message arrive at the destination, they are assembled into the original message. It should be noted that IP datagrams are sent without establishment of communication paths or clearing procedures. Thus, there may be no protection against loss, duplication, misdelivery, and the like. Further with reference to FIG. 2, the IP header 201 includes five 32-bit words, each of which is subdivided into fields, description of which will be made in more detail hereafter. The version field 202, which is four bits, indicates a format of the IP header 201. The IHL field 204 (i.e., internal header length), which is four bits, represents the length of the IP header 201 in 32-bit words. It should be noted that the minimum value for a correct IP header 201 is five (i.e., five 32-bit words). The type of service field 206, which is eight bits, represents an indication of abstract parameters for a quality of service (i.e., “QoS”) to guide selection of actual service parameters when transmitting the datagram 200 through a particular network over the Internet. The total length field 208, which is 16 bits, represents a total length of the datagram 200 in octets (i.e., an octet is 8 bits in length), including both the IP header 201 and data length 207. It should be noted that data 207 of the IP datagram 200 comprises the TCP header 203 and data 205. The identifier field 210, which is 16 bits, represents an identifying value assigned by a sender to aid in assembly of fragments of a datagram, which will be described in greater detail hereinafter. The flags field 212, which is three bits, represents various control flags directed to fragmentation that is described likewise described in greater detail hereinafter. The fragment offset field 214, which is 13 bits, indicates a position of the datagram 200 to which a particular fragment belongs. It should be noted that the fragment offset in field 214 is measured in octets, wherein the fragment offset for a first fragment is zero.
Yet further with regard to FIG. 2, the time to live field 216 (i.e., “TTL”), which is 8 bits, indicates a maximum time that the datagram 200 is allowed to remain on the Internet. It should be noted that is the value of field 216 is measured in seconds and if it reaches zero, the datagram 200 is destroyed. The protocol field 218, which is eight bits, indicates a next level protocol used in the data portion of the datagram, such as TCP protocol described herein below. The header checksum field 220, which is 16 bits, represents a checksum only for the IP header 201 of the datagram 200. The checksum 220 is a simple error-detection scheme in which the datagram 200 is accompanied by a numerical value based on the number of set bits in the IP header 201. It should be noted that since values in various header fields change, the value of field 220 is recomputed and verified at each point where the IP header 201 of datagram 200 is processed. The source address field 222 and destination address field 224, which are 32 bits in length, respectively provide the source and destination addresses for the datagram 200.
Still further with reference to FIG. 2, the TCP header 201 includes six 32-bit words, each of which is subdivided into fields, description of which will be made in more detail hereafter. The source port field 226, which is 16 bits, indicates a source port number. The destination port 228, which is likewise 16 bits, indicates a destination port. In TCP/IP packet-switched networks, the source and destination ports represent endpoint of a logical connection. A port number of 80 is generally used for HTTP (i.e., HyperText Transfer Protocol) traffic. The sequence number field 230 indicates a first data octet in a fragment, except that if SYN is present, the sequence number 320 is ISN+1 (i.e., initial sequence number). The acknowledgement number filed 232, which is 16 bits, is used for error correction and generally contains a value of a next sequence number to be received. The data offset filed 234, which is 4 bits, represents a number of 32-bit words in the TCP header 203. Thus, this number generally indicates where data 205 of datagram 200 begins. The reserved field 236, which is 6 bits in length, represents bits reserved for future use and is presently set to zero. The flags field 238, comprises six control bits, including: 1) urgent pointer field significant (i.e., URG); 2) acknowledgement field significant (i.e., ACK); 3) push function (i.e., PSH); 4) reset the connection (i.e., RST); 5) synchronize sequence numbers (i.e., SYN) and 6) no more data from the sender (i.e., FIN). Window field, which is 16 bits, indicates a number of data octets that the sender of this fragment is willing to accept, beginning with the first octet indicated in the acknowledgement number field 230. The TCP checksum field 242, which is 16 bits, is used for error detection. The urgent pointer field 244 which is 16 bits, represents a current value of the urgent pointer as a positive offset from the sequence number field 230 in this fragment. That is, the urgent pointer points to a sequence number of an octet following urgent data and urgent pointer field 244 is interpreted only if the URG control bit is set in field 238. The options field 246 is a variable length field that represents options that are available. The options field may or may not appear in the datagram. The padding field 248 represents padding that ensures that the TCP header 203 ends on a 32-bit boundary.
FIG. 3 is a prior art high-level illustration 300 of datagram 200 fragmentation. One of the mechanisms of the Internet Protocol (“IP”) routing is fragmentation and reassembly of datagrams. While being transmitted over the Internet via myriad intermediary packet-switched networks, the contents of datagram 200 do not change on the way to its destination unless fragmentation occurs. Every physical network of the Internet has its own limitation on the size of data that it may carry, which is indicated by an associated MTU (i.e., maximum transmission unit). Under some circumstances, particularly when a large datagram must travel through a network with a smaller MTU, the datagram must be divided into a plurality of smaller fragments at appropriate places 302 (i.e., which are also datagrams) within the smaller MTU, such as fragment I 301 and fragment II 303, so that the fragments may travel through the network onto their journey to the destination. This process of division is called fragmentation. Every fragment 301 and 303 includes an IP header HD-I 304 and HD-II 310, and each of which respectively carries data 308 and 312 that is part of data 207 of the original datagram 200. It should be noted that during fragmentation, only a sequentially first fragment 301 includes a TCP header field 306 that receives the TCP header 203 from datagram 200. Conventionally, the IP of the TCP/IP protocol suite, which is generally located at the network layer 106 of the OSI model of FIG. 1 (i.e., layer 3), must accumulate received fragments until enough have arrived to completely reassemble the original datagram 200 via a process called reassembly. The reassembly processes utilizes the identification field 210, flags field 212, the source address 222 and the destination address 224, and the protocol field 218 to identify received fragments for their reassembly into the original datagram 200.
More particularly with regard to FIGS. 3, it should be noted that datagram 200 may be fragmented into a plurality of fragments, which for simplicity are illustrated as two fragments 301 and 303. Content-based routing that today is necessitated by server load-balancing applications, firewalls, and the like, is cumbersome, inefficient and resource intensive with the conventional IP fragmentation and reassembly processes. First, the IP is unable to correctly route fragments of a datagram utilizing content-based routing because all the fragments do not contain the necessary content-based routing information, such as for example the TCP information that is included only in fragment 301 (i.e., sequentially first fragment). Second, fragments may be disordered when they are received, so that the sequentially first fragment 301 (or fragment 303 of FIG. 4) that contains content-based routing information may be received after the other fragment that do not content-based routing information. Lastly, the last fragment 303 may disordered when received, so that it may not be received last, thereby affecting reassembly at the IP layer. That is, the last fragment is utilized to ascertain whether all fragments of datagram 200 have been received based on their respective lengths of data 308, 312.
FIG. 4 is a prior art depiction 400 of a datagram 200 fragmented into three fragments. The datagram 200 comprises an IP header 201 and data 207, which includes a TCP header 203, and data 205. Data 205 includes cookie 404 for content-based routing. In a conventional fragmentation process, the datagram 200 is fragmented into: fragment I 301, which comprises IP header HD-I 304, TCP header 306, and data 308; fragment II 303, which comprises IP header HD-II 310, data 312 that includes cookie 406 (i.e., cookie 404 of datagram 200); and fragment III 305, which comprises IP header HD-III 408 and data 410. It is to be noted that the content-based information necessary for content-based routing, in this case cookie 404, is located in a sequentially second fragment 303.
Today, a solution to the above-identified problems associated with content-based routing in a fragmentation situation is reassembly as described hereinabove. That is, the fragments are first reassembled into the original datagram at a considered layer of the OSI model (i.e., layer 3–layer 7) of FIG. 1, so as to enable content-based routing to be performed based on the now available content-based routing information. The layer at which reassembly occurs depends on system implementation. For example, a simple IP router may reassemble at layer 3 of the OSI model (IP), while a simple server load balancer may reassemble at layer 4 of the OSI model (TCP). Furthermore, a firewall or any other application implementing a TCP End Point or TCP termination necessarily reassembles at layer 4 of the OSI model (TCP). However, conventional reassembly at the foregoing layers has many drawbacks. During conventional reassembly, all fragments necessarily must be stored before the original datagram is reassembled, thereby requiring large amount of memory and slowing content-based routing time, which proportionally increases with reassembly time of the original datagram. Additionally, hardware required for reassembly may not have the capacity to perform such storage.
It is therefore highly desirable to enable content-based routing of fragments at layer 3 through layer 7 of the OSI model, while avoiding time-consuming and resource-consuming reassembly of the fragments at these layers.